/*
 * Copyright (C) 2011 Nicola Bonzanni
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package nl.vu.few.ibivu.jlemon.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;

import nl.vu.few.ibivu.jlemon.NodeIterator;
import nl.vu.few.ibivu.jlemon.NodeMap;
import nl.vu.few.ibivu.jlemon.concepts.Arc;
import nl.vu.few.ibivu.jlemon.concepts.Graph;
import nl.vu.few.ibivu.jlemon.concepts.Node;

public class DfsVisit<N extends Node & Comparable<N>, A extends Arc & Comparable<A>> {
	private GraphVisitor<N, A> visitor;
	private NodeMap<N, Boolean> reachedMap;
	private Graph<N, A> graph;
	private ArrayList<A> stack;
	private int stackHead;

	public DfsVisit(Graph<N, A> graph, GraphVisitor<N, A> visitor) {
		this.graph = graph;
		this.visitor = visitor;
	}

	public void init() {
		stackHead = -1;
		// TODO attach map as handler?
		reachedMap = new NodeMap<N, Boolean>(graph, false);
		stack = new ArrayList<A>(Collections.nCopies(graph.nodeNum(), (A) null));
	}

	// / \brief Adds a new source node.
	// /
	// / Adds a new source node to the set of nodes to be processed.
	// /
	// / \pre The stack must be empty. Otherwise the algorithm gives
	// / wrong results. (One of the outgoing arcs of all the source nodes
	// / except for the last one will not be visited and distances will
	// / also be wrong.)
	public void addSource(N s) {
		if (stackHead >= 0) {
			throw new IllegalStateException();
		}

		if (!reachedMap.get(s)) {
			reachedMap.put(s, true);
			visitor.start(s);
			visitor.reach(s);
			A e = graph.firstOut(s);
			if (e != null) {
				stack.set(++stackHead, e);
			} else {
				visitor.leave(s);
				visitor.stop(s);
			}
		}
	}

	// / \brief Processes the next arc.
	// /
	// / Processes the next arc.
	// /
	// / \return The processed arc.
	// /
	// / \pre The stack must not be empty.
	public Arc processNextArc() {
		A e = stack.get(stackHead);
		N m = graph.target(e);
		
		if (!reachedMap.get(m)) {
			visitor.discover(e);
			visitor.reach(m);
			reachedMap.put(m, true);
			stack.set(++stackHead, graph.firstOut(m));
		} else {
			visitor.examine(e);
			m = graph.source(e);
			stack.set(stackHead, graph.nextOut(stack.get(stackHead)));
		}

		while (stackHead >= 0 && stack.get(stackHead) == null) {
			visitor.leave(m);
			--stackHead;
			if (stackHead >= 0) {
				visitor.backtrack(stack.get(stackHead));
				m = graph.source(stack.get(stackHead));
				stack.set(stackHead, graph.nextOut(stack.get(stackHead)));
			} else {
				visitor.stop(m);
			}
		}
		return e;
	}

	// / \brief Next arc to be processed.
	// /
	// / Next arc to be processed.
	// /
	// / \return The next arc to be processed or INVALID if the stack is
	// / empty.
	public Arc nextArc() {
		return stackHead >= 0 ? stack.get(stackHead) : null;
	}

	// / \brief Returns \c false if there are nodes
	// / to be processed.
	// /
	// / Returns \c false if there are nodes
	// / to be processed in the queue (stack).
	public boolean emptyQueue() {
		return stackHead < 0;
	}

	// / \brief Returns the number of the nodes to be processed.
	// /
	// / Returns the number of the nodes to be processed in the queue (stack).
	public int queueSize() {
		return stackHead + 1;
	}

	// / \brief Executes the algorithm.
	// /
	// / Executes the algorithm.
	// /
	// / This method runs the %DFS algorithm from the root node
	// / in order to compute the %DFS path to each node.
	// /
	// / The algorithm computes
	// / - the %DFS tree,
	// / - the distance of each node from the root in the %DFS tree.
	// /
	// / \pre init() must be called and a root node should be
	// / added with addSource() before using this function.
	// /
	// / \note <tt>d.start()</tt> is just a shortcut of the following code.
	// / \code
	// / while ( !d.emptyQueue() ) {
	// / d.processNextArc();
	// / }
	// / \endcode
	public void start() {
		while (!emptyQueue())
			processNextArc();
	}

	// / \brief Executes the algorithm until the given target node is reached.
	// /
	// / Executes the algorithm until the given target node is reached.
	// /
	// / This method runs the %DFS algorithm from the root node
	// / in order to compute the DFS path to \c t.
	// /
	// / The algorithm computes
	// / - the %DFS path to \c t,
	// / - the distance of \c t from the root in the %DFS tree.
	// /
	// / \pre init() must be called and a root node should be added
	// / with addSource() before using this function.
	public void start(N t) {
		while (!emptyQueue() && !reachedMap.get(t))
			processNextArc();
	}

	// / \brief Executes the algorithm until a condition is met.
	// /
	// / Executes the algorithm until a condition is met.
	// /
	// / This method runs the %DFS algorithm from the root node
	// / until an arc \c a with <tt>am[a]</tt> true is found.
	// /
	// / \param am A \c bool (or convertible) arc map. The algorithm
	// / will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
	// /
	// / \return The reached arc \c a with <tt>am[a]</tt> true or
	// / \c INVALID if no such arc was found.
	// /
	// / \pre init() must be called and a root node should be added
	// / with addSource() before using this function.
	// /
	// / \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
	// / not a node map.
	public A start(Map<A, Boolean> am) {
		while (!emptyQueue() && !am.get(stack.get(stackHead)))
			processNextArc();
		return emptyQueue() ? null : stack.get(stackHead);
	}

	// / \brief Runs the algorithm from the given source node.
	// /
	// / This method runs the %DFS algorithm from node \c s.
	// / in order to compute the DFS path to each node.
	// /
	// / The algorithm computes
	// / - the %DFS tree,
	// / - the distance of each node from the root in the %DFS tree.
	// /
	// / \note <tt>d.run(s)</tt> is just a shortcut of the following code.
	// /\code
	// / d.init();
	// / d.addSource(s);
	// / d.start();
	// /\endcode
	public void run(N s) {
		init();
		addSource(s);
		start();
	}

	// / \brief Finds the %DFS path between \c s and \c t.

	// / This method runs the %DFS algorithm from node \c s
	// / in order to compute the DFS path to node \c t
	// / (it stops searching when \c t is processed).
	// /
	// / \return \c true if \c t is reachable form \c s.
	// /
	// / \note Apart from the return value, <tt>d.run(s,t)</tt> is
	// / just a shortcut of the following code.
	// /\code
	// / d.init();
	// / d.addSource(s);
	// / d.start(t);
	// /\endcode
	public boolean run(N s, N t) {
		init();
		addSource(s);
		start(t);
		return reached(t);
	}

	// / \brief Runs the algorithm to visit all nodes in the digraph.

	// / This method runs the %DFS algorithm in order to
	// / compute the %DFS path to each node.
	// /
	// / The algorithm computes
	// / - the %DFS tree (forest),
	// / - the distance of each node from the root(s) in the %DFS tree.
	// /
	// / \note <tt>d.run()</tt> is just a shortcut of the following code.
	// /\code
	// / d.init();
	// / for (NodeIt n(digraph); n != INVALID; ++n) {
	// / if (!d.reached(n)) {
	// / d.addSource(n);
	// / d.start();
	// / }
	// / }
	// /\endcode
	public void run() {
		init();
		for (NodeIterator<N> it = new NodeIterator<N>(graph); it.hasNext();) {
			it.next();
			if (!reached(it.peek())) {
				addSource(it.peek());
				start();
			}
		}
	}

	// / \name Query Functions
	// / The results of the DFS algorithm can be obtained using these
	// / functions.\n
	// / Either \ref run(Node) "run()" or \ref start() should be called
	// / before using them.

	// /@{

	// / \brief Checks if a node is reached from the root(s).
	// /
	// / Returns \c true if \c v is reached from the root(s).
	// /
	// / \pre Either \ref run(Node) "run()" or \ref init()
	// / must be called before using this function.
	public boolean reached(N v) {
		return reachedMap.get(v);
	}
}
